package com.cjm.algorithm.queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给一个整数数组nums, 数组中共有n个整数。132模式的子序列由三个整数nums[i]、nums[j]和nums[k]组成，
 * 并同时满足：i<j<k和nums[i]<nums[k]<nums[j]
 */
public class Find132pattern456 {
    public boolean find132pattern(int[] nums) {
        // 这个队列的长度是多少？
        int n = nums.length;
        // 一个双端队列
        Deque<Integer> d = new ArrayDeque<>();
        // 记录一个k值, 它是记录最大值的了
        int k = Integer.MIN_VALUE;
        // 从最右侧开始遍历
        for (int i = n - 1; i >= 0; i--) {
            // 如果一个元素的值， 小于k， 那么就有这种值？为什么呢？
            if (nums[i] < k) return true;
            // 这个队列不为空， 并且队列的最上面的元素的值 < 当前的元素值
            while (!d.isEmpty() && d.peekLast() < nums[i]) {
                // 那么去， 找一下， 那个值大些？k的值大些？还是队列最上面的值大些？
                // 大的那个值， 赋值值给到k
                k = Math.max(k, d.pollLast());
            }
            // 将这个元素给放入到队列的最上面去
            d.addLast(nums[i]);
        }
        // 走完了， 找不到， 那么就是找不到喽， 返回false
        return false;
    }
}
